package leetcode_41_60;

import java.util.Arrays;

public class insert_57 {
    /**
     * 一个重叠的 ，按照区间起始端点排序的区间列表。
     * 在列表中插入一个新的区间
     * 需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
     *
     * 1ms  96.75%  但是很繁琐
     * 47行
     * @param intervals  例 [1,3],[6,9]
     * @param newInterval  插入区间  例 [2,5]
     * @return
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length==0){
            int [][] res1=new int[1][];
            res1[0]=newInterval;
            return res1;
        }
        int[][] res = new int[intervals.length+1][2];
        int idx = -1;
        boolean isInsert=false;  //是否已经插入
        for (int i=0 ;i< intervals.length ;i++) {
            if (!isInsert) {
                if (intervals[i][0] < newInterval[0]) //当前区间的起始位置 < 插入区间 的起始位置
                    res[++idx] = intervals[i];   //直接把当前区间放入结果集
                else { //当前区间的起始位置 > 插入区间 的起始位置
                    res[++idx] = newInterval;       //把插入区间 放入结果集
                    isInsert=true;
                    if (newInterval[0] == newInterval[1]) {  //插入数组两个数字相同
                        res[++idx] =intervals[i];
                        continue;
                    }
                }
                if(isInsert){ //已插入
                    if (newInterval[1] <intervals[i][0]) {//插入区间的末尾位置 < 当前区间的起始位置
                        res[++idx] = intervals[i];
                    }else
                        res[idx][1] = Math.max(newInterval[1], intervals[i][1]); //进行合并
                }else { //未插入
                    if (intervals[i][1] >= newInterval[0] ){  //当前区间的末尾位置 >= 插入区间的起始位置
                        res[idx][1] = Math.max(newInterval[1], intervals[i][1]); //进行合并
                        isInsert=true;
                    }
                }
            }
            else {  //已经插入
                if (intervals[i][0] > res[idx][1]) {   //当前区间的起始位置 > 结果数组中最后区间的终止位置
                    for(int t=i;t< intervals.length;t++)//当前区间与结果数组最后一个区间无重叠，后边的区间也不会重叠
                        res[++idx] = intervals[t];
                    break;
                } else {
                    res[idx][1] = Math.max(res[idx][1], intervals[i][1]); //将较大的值作为新的边界值
                }
            }
        }
        if(isInsert==false) //遍历完仍未插入
            res[++idx] = newInterval;
        return Arrays.copyOf(res, idx + 1);//截取有效数组，去掉末尾未使用的空数组
    }

    /**
     * 评论区很丝滑的思路
     * 利用二分查找插入数组的两个数字在原数组的对应位置
     * 将这两个位置之间的元素合并，前后数组保存不变，即为结果
     * 速度与我的相同
     * 25行
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert2(int[][] intervals, int[] newInterval) {
        //newInterval[0]，在第l个数组的范围内
        int l = binarySearch(intervals, newInterval[0], 1);
        //newInterval[1]，在第r个数组的范围内
        int r = binarySearch(intervals, newInterval[1], 0);
        int n = intervals.length;
        int[][] ans = new int[n - r + l + 1][2];  //n - （r - l -1） 即为结果数组的大小
        System.arraycopy(intervals, 0, ans, 0, l); //保存合并数组之前的数组
        if (l != r) {  //将合并后的数组保存到newInterval内
            newInterval[0] = Math.min(intervals[l][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[r-1][1], newInterval[1]);
        }
        //替换l处的数组，丢弃后边已经合并进去的数组
        ans[l] = new int[]{newInterval[0], newInterval[1]};
        System.arraycopy(intervals, r, ans, l + 1, n - r); //保存合并数组之后的数组
        return ans;
    }

    /**
     * 查找数字在，所在二维数组中第几个数组
     * @param arr
     * @param target
     * @param i
     * @return
     */
    int binarySearch(int[][] arr, int target, int i) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr[mid][i] > target) high = mid;
            else if (arr[mid][i] < target) low = mid + 1;
            else return mid + 1 - i;
        }
        return high;
    }
}
